package  main.java.leetcode.editor.cn;
//2022-12-02 17:41:53
//给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。 
//
// 注意：此题 matrix 输入格式为一维 01 字符串数组。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：matrix = ["10100","10111","11111","10010"]
//输出：6
//解释：最大矩形如上图所示。
// 
//
// 示例 2： 
//
// 
//输入：matrix = []
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：matrix = ["0"]
//输出：0
// 
//
// 示例 4： 
//
// 
//输入：matrix = ["1"]
//输出：1
// 
//
// 示例 5： 
//
// 
//输入：matrix = ["00"]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// rows == matrix.length 
// cols == matrix[0].length 
// 0 <= row, cols <= 200 
// matrix[i][j] 为 '0' 或 '1' 
// 
//
// 
//
// 注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode-cn.com/problems/maximal-
//rectangle/ 
// Related Topics 栈 数组 动态规划 矩阵 单调栈 👍 68 👎 0

import java.util.ArrayDeque;
import java.util.Deque;

class PLYXKQ {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new PLYXKQ().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximalRectangle(String[] matrix) {

        if(matrix.length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length();

        int[][] array = new int[m][n];
        for(int i = 0;i<m;i++){
            for (int j = 0;j<n;j++){
                if(matrix[i].charAt(j) == '1'){
                    array[i][j] = (j == 0 ? 0 : array[i][j-1])+1;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i<n;i++){
            Deque<Integer> stack = new ArrayDeque<>();
            int[] up = new int[m];
            int[] down = new int[m];

            for(int j = 0;j<m;j++){
                while (!stack.isEmpty() && array[stack.peek()][i] >= array[j][i]){
                    stack.pop();
                }
                up[j] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(j);
            }
            stack.clear();

            for(int j = m-1;m>=0;j--){
                while (!stack.isEmpty() && array[stack.peek()][i] >= array[j][i]){
                    stack.pop();
                }
                down[j] = stack.isEmpty() ? n : stack.peek();
                stack.push(j);
            }

            for(int j = 0;j<m;j++){
                ans = Math.max(ans,(up[j]-down[j]-1)*array[j][i]);
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
